package com.le.medium.class6;

import org.junit.Test;

/**
 * 找到一棵二叉树中，最大的搜索二叉子树，返回最大搜索二叉子树的节点个数。
 * 情况：
 * 1. 不包含当前节点：在左子树 或者 右子树
 * 2. 包含该节点，左子树+右子树 +1
 */
public class Problem03_BiggestSubBSTInTree {

    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class ReturnType {
        public Node maxBSTHead;
        public int maxBSTSize;
        public int min;
        public int max;

        public ReturnType(Node maxBSTHead, int maxBSTSize, int min, int max) {
            this.maxBSTHead = maxBSTHead;
            this.maxBSTSize = maxBSTSize;
            this.min = min;
            this.max = max;
        }
    }

    public static Node getMaxBST(Node head) {
        return process(head).maxBSTHead;
    }

    private static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        ReturnType leftInfo = process(head.left);
        ReturnType rightInfo = process(head.right);

        int min = Math.min(head.value, Math.min(leftInfo.min, rightInfo.min));
        int max = Math.min(head.value, Math.max(leftInfo.max, rightInfo.max));

        // 可能性1,2 最大节点数目 和 头
        int maxBSTSize = Math.max(leftInfo.maxBSTSize, rightInfo.maxBSTSize);
        Node maxBSTHead = rightInfo.maxBSTSize >= leftInfo.maxBSTSize ? rightInfo.maxBSTHead : leftInfo.maxBSTHead;

        // 考虑可能性3
        if (head.left == leftInfo.maxBSTHead && leftInfo.max < head.value &&
                head.right == rightInfo.maxBSTHead && rightInfo.min > head.value) {
            maxBSTSize = leftInfo.maxBSTSize + rightInfo.maxBSTSize + 1;
            maxBSTHead = head;
        }
        return new ReturnType(maxBSTHead, maxBSTSize, min, max);
    }

    // for test -- print tree
    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }


    @Test
    public void test(){
        Node head = new Node(6);
        head.left = new Node(1);
        head.left.left = new Node(0);
        head.left.right = new Node(3);
        head.right = new Node(12);
        head.right.left = new Node(10);
        head.right.left.left = new Node(4);
        head.right.left.left.left = new Node(2);
        head.right.left.left.right = new Node(5);
        head.right.left.right = new Node(14);
        head.right.left.right.left = new Node(11);
        head.right.left.right.right = new Node(15);
        head.right.right = new Node(13);
        head.right.right.left = new Node(20);
        head.right.right.right = new Node(16);
        printTree(head);
        Node bst = getMaxBST(head);
        printTree(bst);
    }
}
